/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
export var pacificAtlantic = function (heights) {
  const [m, n] = [heights.length, heights[0].length]
  const pacific = new Array(m).fill(0).map(() => new Array(n).fill(0))
  const atlantic = new Array(m).fill(0).map(() => new Array(n).fill(0))

  const dfs = (curr, ocean) => {
    const [row, col] = curr
    if (ocean[row][col]) return
    ocean[row][col] = true
    for (let [dr, dc] of [
      [-1, 0],
      [0, -1],
      [0, 1],
      [1, 0],
    ]) {
      const nr = row + dr
      const nc = col + dc
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue
      if (heights[nr][nc] >= heights[row][col]) dfs([nr, nc], ocean)
    }
  }

  for (let i = 0; i < m; i++) {
    dfs([i, 0], pacific)
    dfs([i, n - 1], atlantic)
  }

  for (let i = 0; i < n; i++) {
    dfs([0, i], pacific)
    dfs([m - 1, i], atlantic)
  }

  const ans = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (pacific[i][j] && atlantic[i][j]) ans.push([i, j])
    }
  }
  return ans
}
